package main

import "fmt"

type NumArray struct {
	value  []int   //线段树的数组结构
	length int     //原数组的长度
}

//建树
func Constructor(nums []int) NumArray {
	tree := NumArray{make([]int, len(nums)<<2), len(nums)-1}   //为线段树开辟4倍空间
	tree.buildTree(nums, 1, 0, tree.length)
	return tree
}
//更新节点
func (this *NumArray) Update(index int, val int) {
	this.update(1, 0, this.length, index, val)
}
//查找区间和
func (this *NumArray) SumRange(left int, right int) int {
	return this.querySum(1, 0, this.length, left, right)
}

//建树, value 是线段树的数组结构， 根据nums数组构建线段树, treeIndex是线段树数组的下标
//left, right 是nums数组的最左和最右
func (this *NumArray) buildTree(nums []int, treeIndex, left, right int) {
	// 递归终止条件, 当left 和 right 重合 就是叶子节点
	if left == right {
		this.value[treeIndex] = nums[left]   //叶子节点直接赋值
		return
	}
	mid := (left + right) >> 1          //一分为二
	treeLeft  := treeIndex << 1     //线段树当前节点的左孩子(n*2 + 1)
	treeRight := treeIndex << 1 | 1     //线段树当前节点的右孩子(n*2 + 2)
	this.buildTree(nums, treeLeft, left, mid)             //递归左子树
	this.buildTree(nums, treeRight, mid+1, right)         //递归右子树
	//后序遍历, 更新当前节点的值为左右子树的和
	this.value[treeIndex] = this.value[treeLeft] + this.value[treeRight]
}

//更新节点自底向上推, treeIndex线段树的下标, left right原数组的左和右, idx  和 val 更新原数组下标和值
func (this *NumArray) update(treeIndex, left, right, idx, val int) {
	if left == right { //找到了叶子节点, 并且当前节点正是idx更新的下标
		this.value[treeIndex] = val   //更新叶子节点的值
		return
	}
	mid := (left + right) >> 1
	treeLeft  := treeIndex << 1
	treeRight := treeIndex << 1 | 1
	if idx <= mid {     //比mid小, 就找左子树
		this.update(treeLeft, left, mid, idx, val)
	} else {            //比mid大, 就找右子树
		this.update(treeRight, mid+1, right, idx, val)
	}
	this.value[treeIndex] = this.value[treeLeft] + this.value[treeRight] //上推更新父亲节点的值
}

func (this *NumArray) querySum (treeIndex, left, right, L, R int) (ans int) {
	fmt.Printf("L=%d  R=%d\n", left, right)
	// 要搜索的区间和当前节点表示的区间没有交集
	if left >= L && right <= R {    //当left 和 right 在查询的区间[L, R]内 直接返回当前节点的值
		return this.value[treeIndex]
	}
	mid := (left + right) >> 1
	if mid >= L {
		ans += this.querySum(treeIndex << 1, left, mid, L, R)
	}
	if R > mid {
		ans += this.querySum(treeIndex << 1 | 1, mid+1, right, L, R)
	}
	return ans
}

func main() {
	arr := []int{1, 3, 5,7,6,11}
	MyTree := Constructor(arr)
	fmt.Println(MyTree.SumRange(2,5))
}